34857번 - 여행

문제

와칠은 은하를 여행하는 여행자다.

와칠이 이번에 여행하려 하는 은하에는 $N$개의 별이 존재한다. 각 별에는 1ドル$부터 $N$까지의 번호가 붙어 있다. 와칠은 이번 여행에서 $N$개의 별을 모두 최소 한 번씩 방문하고 출발지 별로 돌아오려 한다. 시간은 아무리 오래 걸려도 상관없다. 여행 중간에 출발지를 방문해도 되고 어떤 별을 여러 번 방문해도 된다.

이 은하의 별들 사이에는 두 개의 별을 잇는 단방향 웜홀 $M$개가 존재한다. 별들 간의 거리는 매우 멀어서 웜홀을 이용하지 않으면 다른 별로 이동할 수 없다. 하지만 이 웜홀들은 매우 불안정해 특정한 주파수의 물체만 통과시킨다. $i$번째 웜홀을 통과할 수 있는 요구 주파수는 $\lambda_{i}$이다. 한 별에 웜홀이 너무 많으면 시공간이 붕괴하기에 각 별당 웜홀의 출입구는 합해서 최대 10ドル$개까지 있을 수 있다.

와칠은 각 별에서 에너지를 흡수하거나 방출해 우주선의 주파수를 변경할 수 있다. 에너지를 $E_{a}$만큼 흡수하면 주파수는 $E_{a}$만큼 증가하고 에너지를 $E_{b}$만큼 방출하면 주파수는 $E_{b}$만큼 감소한다. 주파수는 1ドル$보다 줄어들 수 없다. 따라서 현재 우주선의 주파수가 $E_{b}$를 넘을 때만 에너지를 $E_{b}$만큼 방출할 수 있다.

양자적 문제로 인해 $i$번째 별에서 한 번에 흡수할 수 있는 에너지의 양과 한 번에 방출할 수 있는 에너지의 양은 각각 $EI_{i}$와 $EO_{i}$로 제한되지만 한 별에서 연속적으로 여러 번 에너지를 흡수하거나 방출할 수 있다. 또한 와칠의 우주선의 주파수가 특정 웜홀과 일치하더라도 웜홀을 통과하지 않고 특정 별에서 계속해 에너지를 흡수하거나 방출할 수 있다.

모든 $N$개의 별에 대해서, 각 별을 출발지 별로 지정했을 때 $N$개의 별을 모두 최소 한 번씩 방문하고 출발지 별로 돌아올 수 있는지 판정하여라. 우주선의 처음 주파수는 마음대로 설정할 수 있지만, 출발지에서 여행을 종료할 때의 주파수가 우주선의 처음 주파수와 일치해야 한다.

입력

첫째 줄에 별의 수 $N$과 웜홀의 수 $M$이 공백으로 구분되어 주어진다. (2ドル \le N \le 10^{5};$ 0ドル \le M \le 5 \times 10^{5}$)

이후 $N$개의 줄에 걸쳐 $i$번째 줄에는 $i$번째 별에서 흡수할 수 있는 에너지 $EI_{i}$와 방출할 수 있는 에너지 $EO_{i}$가 공백으로 구분되어 주어진다. (1ドル \le EI_{i}, EO_{i} \le 10^{9}$)

이후 $M$개의 줄에 걸쳐 $i$번째 줄에는 별 번호 $U_{i},ドル $V_{i}$와 주파수 $\lambda_{i}$가 공백으로 구분되어 주어진다. 이는 $U_{i}$번 별에서 $V_{i}$번 별으로 향하는 요구 주파수 $\lambda_{i}$의 웜홀이 존재함을 의미한다. (1ドル \le U_{i}, V_{i} \le N;$ $U_{i} \neq V_{i};$ 1ドル \le \lambda_{i} \le 10^{9}$)

입력되는 모든 수는 정수이다.

출력

$N$개의 줄에 걸쳐 $i$번째 줄에는 와칠이 $i$번 별을 출발지 별로 하였을 때 은하의 모든 별을 방문하고 출발지 별로 돌아올 수 있다면 1ドル,ドル 아니라면 0ドル$을 출력한다.

제한

노트