410060: GYM103934 H Tomb of Tutankhamun

Ahmed lived his entire live in Egypt, and since he was a kid one of his only missions was to keep the secrets of the the tomb of Tutankhamun and going to the ICPC World Finals. Unfortunately, while he was outside the Valley of the Kings for a competition, the great archeologist Mohamed visited the tomb, and, without Ahmed to stop him, found a secret room with never-before-seen paintings about different periods in Egyptian history.

Ahmed realised that he can use this opportunity to share knowledge about the history of Egypt, but he will have to be careful to do so without leaking too many secrets.

To study the $$$n$$$ paintings that were found, Mohamed will send $$$n$$$ historians. He gave Ahmed a list of $$$m$$$ triples $$$(h_i,p_i,c_i)$$$, indicating that the historian $$$h_i$$$ knows the period represented in the painting $$$p_i$$$ with a knowledge level of $$$c_i$$$. This level may be $$$0$$$, indicating a weak knowledge, or $$$1$$$, indicating a strong knowledge. If, for some $$$h_i$$$ and $$$p_i$$$, no triple $$$(h_i,p_i,c_i)$$$ is in the list, $$$h_i$$$ does not know the period $$$p_i$$$. It is guaranteed that for any $$$h_i$$$ and $$$p_i$$$, at most one triple $$$(h_i,p_i,c_i)$$$ is in the list.

Ahmed will choose paintings for the historians to study, and he will do so in such a way that at each historian studies at most one painting and at most one historian studies each painting. A historian can only study a painting if they know the period in it.

Ahmed knows that only a strong knowledge on the period of a painting will bring on new knowledge about Egypt, so he will be happy with his own choice if and only if exactly $$$k$$$ historians have strong knowledge on the period of the painting they are studying.

Mohamed knows that, given the list of triples, regardless of how Ahmed makes his choice, at most $$$E$$$ historians will study some paintings. He calls all choices in which exactly $$$E$$$ historians study some painting of maximum choices.

To keep Ahmed happy, he guarantees that there is at least one maximum choice in which at most $$$k$$$ historians have strong knowledge on the period on the painting they are studying, and there is at least one maximum choice in which at least $$$k$$$ historians have strong knowledge on the period on the painting they are studying.

Since Mohamed does not trust Ahmed's skills very much, he will be happy either with a maximum choice, or an almost-maximum choice, i.e., a choice in which $$$E-1$$$ historians know the period represented in the painting they are studying.

Ahmed now comes to ask for your help to find a maximum, or almost-maximum choice, in which exactly $$$k$$$ historians have a strong knowledge of the period of the painting they are studying. It is guaranteed that such choice exists.

The first line of input contains $$$n, m, k$$$ ($$$1 \leq n \leq 500$$$)($$$1 \leq m \leq min(n^2, 10^5)$$$)($$$0 \leq k \leq n$$$).

Following thatm $$$m$$$ lines containing $$$h_i, p_i, c_i$$$ with ($$$1 \leq h_i,p_i \leq n$$$) and $$$c_i \in \{0, 1\}$$$.

The first line of output must contain a number $$$E'$$$, indicating the number of historians that will study some painting.

The $$$E'$$$ following lines must contain pairs $$$(h_i,p_i)$$$, indicating that historian $$$h_i$$$ will study the painting $$$p_i$$$ in Ahmed's choice.

3 7 2
1 1 0
2 2 0
3 3 0
1 2 1
2 1 1
2 3 1
3 2 1

3
1 1
2 3
3 2

2 4 2
1 1 1
1 2 0
2 1 0
2 2 1

2
1 1
2 2