题目背景

小 C 拉小 L 去走亲戚。

题目描述

小 C 共有 $n$ 个亲戚，某些亲戚家之间有 $m$ 条双向的道路，保证亲戚家之间两两可达。

小 C 要亲自去走亲戚。具体的，小 C 一开始在第 $s$ 个亲戚家。每次她可以前往一个与她现在的位置有道路相连的亲戚家。然而小 C 太有魅力了。每当她走过一条道路时，追求她的人便会从四面八方涌来，导致这条路堵车。当然，她也可以躲在车里面，收起她的迷人魅力，这样这条路就不会堵车了。

因为小 L 是路痴，所以小 C 希望最后剩下尽量少的 $n-1$ 条没有堵车的道路，并使得只保留着 $n-1$ 条道路后，亲戚家之间仍两两可达。

因为小 C 不想四处奔波这么久，所以最多只会走过 $k$ 条道路。

请你为她输出一种走亲戚的方案。

形式化题意

给定一个 $n$ 个点 $m$ 点边的简单无向连通图，你需要构造一组满足下面要求的路径：

• 起点为 $s$，终点不限。

• 对于走过的每一组边 $(u_i,v_i)$，你需要额外决定 $p_i\in\{0,1\}$，满足：

1. $p_i=0$ 表示删除这条边，且不能再使用，即之后不能再次经过这条边；$p_i=1$ 表示不删除这条边。

2. 如果 $i>1$，那么 $u_i=v_{i-1}$。即使 $p_i=0$，也需要满足这条限制。

• 路径的长度不能超过 $k$。

• 最后未删除的边组成一棵 $n$ 个节点的树。

特别的，一组边在被删除前可以经过多次。

若有多组满足条件的路径，可以输出任意一组。

可以证明在本题的限制条件下，一定存在合法的方案。

输入格式

第一行输入四个整数 $n,m,k$ 和 $s$。

接下来 $m$ 行每行输入整数 $u$ 和 $v$，表示第 $u$ 个亲戚家和第 $v$ 个亲戚家之间有一条双向道路。

输出格式

第一行输出一个整数，表示走过的道路的数量。

接下来若干行输出你的方案。具体的，每行输出两个整数。第一个整数表示道路的编号，第二个整数的值为 $0$ 或 $1$，若是 $0$ 表示让这条路堵车（删除这条边），若是 $1$ 表示让这条路保持畅通（保留这条边）。

如果有多种方案，任意输出一种也将被视为正确。

5 5 10 4
1 3
2 5
2 3
4 5
1 5

2
4 1
2 0

提示

样例解释

首先我们从第 $4$ 条道路后到达 $5$ 号亲戚家，再通过第 $2$ 条道路到达 $2$ 号亲戚，并让第 $2$ 条道路堵车。此时，只剩下 $n-1$ 条没有堵车的道路，并且亲戚家之间仍然两两可达。

对于以下输出：

2
4 1
5 0

或者以下输出：

3
4 1
2 1
3 0

也将视作正确。

数据范围

本题采用捆绑测试。

对于 $100\%$ 的数据，$n-1\le m\le\dfrac{n(n-1)}{2}$，$1\le u,v \le n$，且图中无自环、重边。

后话：这并非此题的原版，而是改版。然而原版我们目前并没有想到做法，有思路可以联系 Down_syndrome。