Spanning Tree Walk

In this problem, you are given a simple, undirected, connected graph with (n) nodes and (m) edges. Each edge represents a road between the houses of C's relatives. C starts at node (s) and will traverse at most (k) edges. For every edge she traverses, she must choose a value (p) (either 0 or 1) with the following meaning:

• \(p = 0\) indicates that she deletes (blocks) that edge permanently. In addition, a blocked edge cannot be used again in subsequent moves.
• \(p = 1\) means she leaves the edge intact (does not block it).

Moreover, if she traverses an edge on the (i)-th move from node (u_i) to (v_i), then for all moves with (i > 1) it must hold that (u_i = v_{i-1}).

After she finishes her walk (which consists of at most (k) moves), the set of edges that were never blocked (i.e. those with (p = 1) when traversed) must form a spanning tree on all (n) nodes. Note that even if an edge is traversed multiple times before it is blocked, if it is never blocked it contributes to the final spanning tree.

A valid solution always exists under the constraints given. Your task is to output one valid walk plan.

Input Format (see below):

• The first line contains four integers: \(n\), \(m\), \(k\), and \(s\) (the starting node).
• Each of the following \(m\) lines contains two integers representing an undirected edge between two nodes.

Output Format (see below):

• First print an integer \(L\), the number of moves (edges traversed) in your walk (\(L\) must be \(\le k\)).
• Then print \(L\) lines, each containing three integers \(u\), \(v\), and \(p\), representing a move from node \(u\) to node \(v\) and the decision \(p\) (with \(p = 1\) meaning keeping the edge, which is what you should do to form a spanning tree).

Idea: One simple approach is to select any spanning tree of the given graph (which exists because the graph is connected) and then output a DFS traversal of that spanning tree starting at node (s). When moving along an edge of the spanning tree, output a move with (p = 1). When backtracking (which is allowed because a non‐deleted edge may be used multiple times), also output (p = 1). Thus, the final set of not blocked edges will exactly be the spanning tree.

Note: It is guaranteed that the provided (k) is large enough (for instance, it is at least (2(n-1))) so that a DFS traversal on the spanning tree is possible.

inputFormat

The input begins with a line containing four integers \(n\), \(m\), \(k\), and \(s\), where:

• \(n\) is the number of nodes (relatives).
• \(m\) is the number of undirected edges (roads).
• \(k\) is the maximum number of edges C is willing to traverse.
• \(s\) is the starting node.

Then \(m\) lines follow, each containing two integers \(u\) and \(v\) indicating an edge between nodes \(u\) and \(v\). It is guaranteed that the graph is simple and connected.

outputFormat

First, print an integer \(L\) (\(L \le k\)), representing the total number of moves. Then print \(L\) lines. Each line should contain three integers \(u\), \(v\), and \(p\) describing one move:

• \(u\): the current node.
• \(v\): the next node to move to (\(v\) must be adjacent to \(u\)).
• \(p\): a flag where \(p = 1\) means the edge is kept (not blocked) and \(p = 0\) means the edge is blocked (deleted), and blocked edges cannot be used again.

The moves must satisfy that for every move after the first, the starting node equals the ending node of the previous move. Finally, the set of edges that were never blocked (i.e. those where \(p = 1\)) should form a spanning tree on all \(n\) nodes.

sample

3 3 4 1
1 2
2 3
1 3

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

</p>