어지러운 소들

소들이 농장 안에서 서로 달리기 경주를 시작했는데, 원을 그리며 돌면 어지러워지고, 어지러운 소는 우유를 내지 않습니다. 그래서 농부 존은 모든 양방향 길을 일방통행 길로 바꾸어, 소가 출발한 자리로 다시 돌아오는 사이클이 농장에 하나도 남지 않게 하려고 합니다. 사이클이란 한 개 이상의 길을 지나 처음 출발한 목초지로 되돌아오는 경로를 말합니다.

농장에는 $1$번부터 $N$번까지 번호가 매겨진 $N$개의 목초지가 있습니다 ($1 \le N \le 10^5$). 이 목초지들은 $M_1$개의 일방통행 길 ($1 \le M_1 \le 10^5$)과 $M_2$개의 양방향 길 ($1 \le M_2 \le 10^5$)로 이어져 있습니다. 어떤 길도 한 목초지를 자기 자신과 잇지는 않지만, 서로 다른 두 목초지를 여러 개의 길이 이을 수는 있습니다. 또한 임의의 두 목초지 사이를 반드시 오갈 수 있는 것은 아닙니다.

각 일방통행 길은 목초지 $A_i$에서 목초지 $B_i$로 향합니다 ($1 \le A_i, B_i \le N$). 각 양방향 길은 목초지 $X_i$와 $Y_i$를 잇습니다 ($1 \le X_i, Y_i \le N$). 일방통행 길들은 이미 사이클을 이루지 않음이 보장되며, 방향을 바꾸지 않고 그대로 두어야 합니다. 여러분이 할 일은 모든 양방향 길에 방향을 정하여, 이제 일방통행 길로만 이루어진 농장 전체에 사이클이 없도록 만드는 것입니다.

예를 들어, 양방향 길이 목초지 $1$과 $3$, $2$와 $3$, $2$와 $4$를 잇고, 일방통행 길이 $1$에서 $2$로, $4$에서 $3$으로 향한다고 합시다:

1-->2
|  /|
| / |
|/  |
3<--4

양방향 길을 $1 \to 3$, $2 \to 3$, $2 \to 4$의 방향으로 정하면 농장에 사이클이 남지 않습니다:

1-->2
|  /|
| / |
v   v
3<--4

• 첫째 줄: 공백으로 구분된 세 정수 $N$, $M_1$, $M_2$.
• $2 \ldots 1 + M_1$번째 줄: 각 줄에 공백으로 구분된 두 정수 $A_i$와 $B_i$가 주어지며, $A_i$에서 $B_i$로 향하는 일방통행 길을 나타냅니다.
• $2 + M_1 \ldots 1 + M_1 + M_2$번째 줄: 각 줄에 공백으로 구분된 두 정수 $X_i$와 $Y_i$가 주어지며, $X_i$와 $Y_i$를 잇는 양방향 길을 나타냅니다.

다음의 정해진 규칙으로 양방향 길의 방향을 정합니다. 이 규칙에 따르면 답이 유일하게 결정됩니다.

1. 일방통행 길만 살펴봅니다. 현재 들어오는 일방통행 길이 하나도 없는 목초지 중 번호가 가장 작은 것을 골라 순서 목록의 끝에 추가한 뒤, 그 목초지와 거기서 나가는 일방통행 길을 제거합니다. 이 과정을 반복하면 일방통행 부분 그래프의 위상 정렬 중 사전순으로 가장 앞서는 것이 만들어집니다.
2. 각 양방향 길은 두 끝점 중 이 순서에서 더 앞에 오는 목초지에서 더 뒤에 오는 목초지로 향하도록 방향을 정합니다.

$M_2$개의 줄을 출력합니다. $i$번째 줄에는 공백으로 구분된 두 정수, 즉 방향이 정해진 $i$번째 양방향 길의 시작 목초지와 도착 목초지를 출력합니다. 양방향 길은 입력과 같은 순서로 나타나야 합니다.

만약 일방통행 길 자체가 사이클을 이루어 유효한 방향 배정이 존재하지 않는다면, 대신 한 줄에 -1을 출력합니다.