Come and Go#6933
In a certain city there are intersections connected by one-way and two-way streets. It is a modern city, and several of the streets have tunnels or overpasses. Evidently it must be possible to travel between any two intersections. More precisely given two intersections and it must be possible to travel from to and from to .
Your task is to write a program that reads a description of the city street system and determines whether the requirement of connectedness is satisfied or not.
The input contains several test cases. The first line of a test case contains two integers and , separated by a space, indicating the number of intersections (2 \le N \le 2000) and number of streets (2 \le M \le N(N - 1)/2). The next lines describe the city street system, with each line describing one street. A street description consists of three integers , and , separated by a blank space, where and are distinct identifiers for intersections (1 \le V, W \le N, V \ne W) and can be or ; if P = 1 the street is one-way, and traffic goes from to ; if P = 2 then the street is two-way and links and . A pair of intersections is connected by at most one street.
The last test case is followed by a line that contains only two zero numbers separated by a blank space.
For each test case print one in a separate line if the condition of connectedness is satisfied, and zero otherwise.
Example 1