P11762 [IAMOI R1] 走亲访友
题目背景
小 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$ 个节点的树。
特别的，一组边在被删除前可以经过多次。
若有多组满足条件的路径，可以输出任意一组。
可以证明在本题的限制条件下，一定存在合法的方案。
输入格式
无
输出格式
无
说明/提示
### 样例解释
首先我们从第 $4$ 条道路后到达 $5$ 号亲戚家，再通过第 $2$ 条道路到达 $2$ 号亲戚，并让第 $2$ 条道路堵车。此时，只剩下 $n-1$ 条没有堵车的道路，并且亲戚家之间仍然两两可达。
对于以下输出：
```
2
4 1
5 0
```
或者以下输出：
```
3
4 1
2 1
3 0
```
也将视作正确。
### 数据范围
**本题采用捆绑测试**。
| Subtask | $n\le$ | $m$ | $k=$ | 分数 |
| :----------: | :----------: | :----------: | :----------: | :----------: |
| 1 | $10$ | $\le 10$ | $100$ | $20$ |
| 2 | $100$ | $\le \frac{n(n-1)}{2}$ | $10^6$ | $10$ |
| 3 | $10^3$ | $=n$ | $n+m$ | $10$ |
| 4 | $10^3$ | $\le \frac{n(n-1)}{2}$ | $n^2$ | $20$ |
| 5 | $10^3$ | $\le \frac{n(n-1)}{2}$ | $n+m$ | $40$ |
对于 $100\%$ 的数据，$n-1\le m\le\dfrac{n(n-1)}{2}$，$1\le u,v \le n$，且图中无自环、重边。
后话：这并非此题的原版，而是改版。然而[原版](https://www.luogu.com.cn/problem/T565042)我们目前并没有想到做法，有思路可以联系 [Down_syndrome](https://www.luogu.com.cn/user/984018)。