1773 - [Usaco2009 Dec]Dizzy 头晕的奶牛

Input

  • 第1行: 三个由空格隔开的正数: N, M1和M2 第2到1+M1行: 第i+1行表示第i条单向道路，包含两个由空格隔开的整数: A_i和B_i 第2+M1到第1+M1+M2行: 第i+M1+1行表示第i条单向道路，包含两个由空格隔开的整数 X_i和Y_i

Output

  • 第1到M2行: 第i行应该包含两个由空格隔开的整数: 根据你给第i条双向道路定义的的方 向，可能是X_i, Y_i，也可能是Y_i, X_i。这些双向道路必须按照输入的顺序 输出。如果无解，在单独的一行内输出"-1"。

Examples

Input

4 2 3
1 2
4 3
1 3
4 2
3 2

Output

1 3
2 4
2 3
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题