Byteotia 有 $n$ 个城镇。一些城镇对之间由双向道路连接。道路仅在端点处相交，因此不会交叉；这得益于隧道和立交桥系统。

著名的自行车赛“环 Byteotia 赛”即将开始。已知比赛路线将沿着某些 Byteotian 道路行进，起点和终点在同一个城镇，且每条道路最多经过一次。

Byteasar 是一位著名的 Byteotian 车迷，也是 Byties 足球迷俱乐部的负责人。Byteasar 和他的俱乐部伙伴们厌恶所有的自行车比赛。他们想要封锁一些道路，使得比赛路线无法经过他们居住的城镇。Byteasar 知道他的俱乐部成员居住在哪些城镇。他想要确定需要封锁的最小道路集合，以防止比赛经过任何他的俱乐部伙伴（包括他自己）居住的城镇；明确地说：对于每一个这样的城镇，比赛都不能经过它。你的任务是帮助 Byteasar 找到合适的道路集合。

输入格式

标准输入的第一行包含三个整数 $n$、$m$ 和 $k$ ($1 \le n \le 1\,000\,000$, $0 \le m \le 2\,000\,000$, $1 \le k \le n$)，用空格分隔，分别表示：城镇数量、道路数量以及俱乐部成员居住的城镇数量。城镇编号从 $1$ 到 $n$，其中俱乐部成员居住的城镇编号为 $1$ 到 $k$。接下来的 $m$ 行，每行包含两个整数 $a_{i}$ 和 $b_{i}$ ($1 \le a_{i} < b_{i} \le n$)，用空格分隔，表示城镇 $a_{i}$ 和 $b_{i}$ 之间有一条双向道路。每对 Byteotian 城镇之间最多直接连接一条道路。

在总分 $40\%$ 的测试点中，额外满足 $n \le 1\,000$ 且 $m \le 5\,000$。

输出格式

你的程序应输出一个基数最小的道路集合，封锁这些道路可以防止比赛经过任何俱乐部成员居住的城镇。

程序应在输出的第一行打印这个最小基数。在接下来的行中，指定需要封锁的道路集合，每行一条道路。对于给定的道路，应打印它连接的两个城镇编号，较小的编号在前，两个数字之间用空格分隔。

如果存在多个解，你的程序可以任意选择一个。

样例

输入 1

11 13 5
1 2
1 3
1 5
3 5
2 8
4 11
7 11
6 10
6 9
2 3
8 9
5 9
9 10

输出 1

3
2 3
5 9
3 5