오고 가기

어떤 도시에 교차로가 $N$개 있고, 교차로 사이는 일방통행 도로와 양방향 도로로 이어져 있다. 도로 상당수가 터널을 지나거나 고가로 놓여 있다.

이 도시의 도로망은 어떤 두 교차로 $V$와 $W$를 골라도 $V$에서 $W$로 갈 수 있고 $W$에서 $V$로도 돌아올 수 있어야 한다.

도시의 도로망 정보를 읽어 이 조건이 만족되는지 판정하는 프로그램을 작성하라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 교차로의 수 $N$과 도로의 수 $M$이 공백 하나로 구분되어 주어진다($2 \le N \le 2000$, $2 \le M \le N(N-1)/2$). 이어지는 $M$개의 줄에는 도로 하나의 정보가 정수 세 개 $V$, $W$, $P$로 공백 하나씩 구분되어 주어진다. $V$와 $W$는 서로 다른 교차로 번호이고($1 \le V, W \le N$, $V \ne W$), $P$는 1 또는 2이다. $P$가 1이면 그 도로는 $V$에서 $W$로만 갈 수 있는 일방통행이다. $P$가 2이면 그 도로는 $V$와 $W$를 양방향으로 잇는다. 같은 두 교차로를 잇는 도로가 두 개 이상 주어지는 경우는 없다.

마지막 테스트 케이스 다음 줄에는 공백으로 구분된 0 두 개만 주어진다. 이 줄은 처리하지 않는다.

각 테스트 케이스마다 정수 $G$를 한 줄에 출력한다. 연결 조건이 만족되면 $G$는 1이고, 그렇지 않으면 0이다.