실험

비테크와 친구들은 개미를 위한 미로를 만들고 있습니다. 이 미로에는 $0$번부터 $N-1$번까지 번호가 매겨진 $N$개의 방이 있고, 방들은 일방통행 통로로 연결됩니다. 개미를 어떤 방에 놓으면, 개미는 매 순간 지금 있는 방에서 나가는 통로 중 하나를 무작위로 골라 계속 이동하며, 나가는 통로가 하나도 없는 방에 도착해야만 멈춥니다.

일부 통로는 이미 방향이 정해져 있고, 나머지 통로는 파여 있지만 아직 방향이 정해지지 않았습니다. 방향이 정해지지 않은 모든 통로의 방향을 정해서 어떤 개미도 영원히 돌아다닐 수 없도록 만드는 것이 목표입니다. 즉, 모든 통로의 방향이 정해진 뒤 미로 전체에 방향 순환(사이클)이 하나도 없어야 합니다.

첫째 줄에 세 정수 $N$, $A$, $B$ ($1 \le N, A, B \le 200000$)가 주어집니다. 각각 방의 개수, 방향이 이미 정해진 통로의 개수, 방향이 아직 정해지지 않은 통로의 개수입니다.

다음 $A$개의 줄에는 각각 두 정수 $S$와 $K$가 주어지며, 방 $S$에서 방 $K$로 향하는, 방향이 정해진 통로를 나타냅니다.

이어지는 $B$개의 줄에는 각각 두 정수 $S$와 $K$가 주어지며, 방 $S$와 방 $K$를 잇는, 방향이 정해지지 않은 통로를 나타냅니다.

모든 통로에서 $S \ne K$입니다. 올바른 방향 배정이 항상 존재함이 보장됩니다. 이는 방향이 이미 정해진 통로들만으로는 방향 순환이 생기지 않는다는 뜻과 같습니다.

어떤 개미도 영원히 돌아다니지 못하게 하는 방향 배정은 여러 가지일 수 있으므로, 답을 유일하게 만들기 위해 다음과 같이 정의되는 하나의 방향 배정을 구합니다.

방향이 이미 정해진 통로들만 살펴봅니다. 올바른 배정이 존재하므로 이 통로들은 방향 비순환 그래프를 이룹니다. 다음 과정으로 방들의 표준 순서를 만듭니다. 각 방의 진입 차수를 방향이 정해진 통로만으로 세면서, 현재 진입 차수가 $0$인 방 중 번호가 가장 작은 방을 골라 순서의 맨 뒤에 붙이고, 그 방에서 나가는 방향이 정해진 통로들을 제거합니다(도착하는 방의 진입 차수를 $1$씩 줄입니다). 이 과정을 거치면 모든 방은 서로 다른 위치를 갖게 됩니다.

그런 다음 입력에 주어진 순서대로, 방향이 정해지지 않은 각 통로에 대해 한 줄씩 출력합니다.

• 순서에서 $S$가 $K$보다 앞에 오면 0을 출력합니다(통로를 $S$에서 $K$ 방향으로 정함).
• 그렇지 않으면 1을 출력합니다(통로를 $K$에서 $S$ 방향으로 정함).

이 순서에서 앞선 방에서 뒤에 오는 방으로 모든 통로의 방향을 정하면 어떤 개미도 영원히 돌아다닐 수 없음이 보장됩니다.