Description

Xiao C has $n$ relatives connected by $m$ bidirectional roads, ensuring all relatives are mutually reachable.

Xiao C will personally visit them starting from the $s$-th relative's home. Each time she can move to a relative's home connected by a road. However, whenever she traverses a road, admirers swarm in causing congestion. She can choose to hide her charm (marking $p_i=1$) to prevent congestion, otherwise (marking $p_i=0$) the road becomes permanently blocked after this traversal.

Xiao L is bad with directions, so Xiao C wants to leave exactly $n-1$ unblocked roads forming a connected tree, while traversing at most $k$ roads. Construct such a traversal plan.

Formal Problem Statement

Given a simple undirected connected graph with $n$ nodes and $m$ edges, construct a path satisfying:

1. Starts at node $s$ (end node unrestricted).
2. For each traversed edge $(u_i, v_i)$, assign $p_i \in \{0,1\}$ where:
   • $p_i=0$: Delete this edge (cannot be reused).
   • $p_i=1$: Keep this edge.
   • Path continuity: $u_i = v_{i-1}$ for $i>1$ (even if edge is deleted).
3. Path length ≤ $k$.
4. Remaining edges form a spanning tree.

Multiple traversals allowed before deletion. Solution always exists under given constraints.

Input Format

• First line: four integers $n$, $m$, $k$, $s$.
• Next $m$ lines: two integers $u$ and $v$ per line, representing a bidirectional road.

Output Format

• First line: integer $t$ (number of traversed edges).
• Next $t$ lines: two integers per line - edge index (1-based input order) and $p_i$ (0/1).

Any valid solution is accepted.

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

2
4 1
2 0

Hint

After traversing edge 4 (keep) to node 5, then edge 2 (block), remaining edges form a tree. Alternative solutions like

2
4 1
5 0

or

3
4 1
2 1
3 0

are also valid.

Constraints

Subtask scoring

For 100% data:

• $n-1 \le m \le \frac{n(n-1)}{2}$
• No self-loops or duplicate edges

Postscript: This is a modified version. The original problem remains unsolved. Contact Down_syndrome for ideas.

Translation by DeepSeek R1