* Clarification in problem statements: For any pair of crossroads no two segments of the same category connect these crossroads.
* Tests not satisfing this condition are corrected.
* The first test is changed to the sample from the problem statements.
* New time limit is 2.5 seconds (old time limit was 3 seconds).
* New memory limit is 64 MB (old memory limit was 16 MB).
* New tests are added

All solutions are rejudged. More than 100 authors lost AC during this rejudge.

Sample test
0 2 0
0 2 1

is this true?

Yes, of course!