+ Time Limit : 2 second + Memory Limit : 256 megabytes --------------------- *Shengdebao* is quite a dreamer, thereby dreams a lot! In a dream he had last night people built a whole city named *"Shengdepolis"* in his favour! For the opening of this magnificent city people invited him on a tour expressing the city's impressive features. *Shengdebao* started describing it for you: I entered the city and the first thing I noticed was $n$ towers, some of them were glowing with a beautiful purple light. There were some elevated railroads between some pairs of towers, each railroad was between two **distinct** towers. Some of the railroads were *magical* meaning they could disappear! The highlighted thing was the city's diverse architecture. The lighting of the towers were related to the visible railways. By paying close attention I found out that at any point of time a tower glows purple only when there are **Odd number of visible railroads** connected to them. Some of the railways aren't magical and so are always visible, these railroads are always counted in their adjacent towers. Their tour program was also interesting! The tour contained a set of **turns**, in each *turn* I start by observing the city from a purple luminous tower. A helicopter then comes and takes me to **another glowing** tower. In **both before and after the trip with the helicopter** I take a glance at the landscape. Then after I've took a glance at the landscape on the second tower, the magic happens! some of the magical railroads appear and some disappear, leading to a change in the city's lighting (it is possible that the city doesn't change at all), but the change **must** be in a way that the tower I'm on top of **stays luminous** (meaning **odd** number of **visible** railways should stay connected to it). After the change, the *turn* ends starting a new turn afterwards or ending the tour. These turns start from one Tower and **should end at the same tower**. I remember agreeing to this tour in two conditions: + For **all possible ways of architectures** (meaning the ways which magical railways are visible or not) and **every glowing tower in that form** I should have a view of the city from the top of that tower. meaning if we have $x$ magical railways, for all $2^x$ possible city formats and each glowing tower in every format I should have **at least one** glance of that landscape in either before or after my trip with the helicopter in a *turn*. + The number of *"turns"* should be minimized. The story ends! *Shengdebao* has an identical memory and remembers each detail about the magical city. But he didn't keep track of the number of *turns* in his tour so you should help him find out a valid tour with minimum size. Also if the number of *turns* in the dreamy tour is more than $1\ 000\ 000$ the fact that *Shengdebao* is lying about his dream is in prospect! so if there is no tour with less than $1\ 000\ 000$ *turns*, you should say he is lying! # Input In the input *Shengdepolis* is given. First line contains $n , m$ the number of towers and railways respectively. Then in the next $m$ lines the explanation of each railroad is given by three integers $t , u , v$. $t$ is either $0$ or $1$ if it is $0$ it means that the railway between towers number $v$ and $u$ is **not magical** and if $t = 1$ then it is **magical**. $$1 \le n , m \le 17$$ $$0 \le t \le 1 , 1 \le u , v \le n , u \neq v$$ It is possible for two railways to be **exactly the same**. # Output In the first line of output you should write the minimum number of *turns* in the imaginary tour represented as a number $k$. Then if $k$ is greater than $1\ 000\ 000$ you should display *"lie"* and end the program. If the condition $k \le 1\ 000\ 000$ holds you should output $k$ lines each consisting of 3 integers $u , mask , v$. $u$ represents the tower on which *Shengdebao* starts that *turn* and $v$ shows the one which he ends at after riding the helicopter. $mask$ is a code showing the architecture of the city. A code of a city format is described below: $mask$ is a number less than $2 ^ m$ that when written in the binary notation the $i$th bit is either equal to $0$ or $1$ if it is equal to $0$ it means that the $i$th edge is **invisible** in this form and otherwise this bit is $1$. The number of each edge is **in the order appeared in the input**. By this explanation there **does not exist** any $mask$ in which its $i$th bit is $0$ with also the first integer in the $i+1$th line of input being $0$ at the same time. To clarify, in each line $u$ and $v$ both have **Odd** number of visible railways connected to them in the format coded as $mask$. The $i$th line's third number should be equal to the $i+1$th line's first number and the first number of the first line should be equal to the last number of the $k$th line. If there are multiple tours satifsying the criteria, you can output an arbitrary one. # Examples ## Sample input 1 ``` 3 2 0 1 2 0 2 3 ``` ## Sample output 1 ``` 2 1 3 3 3 3 1 ``` *Explanation:* No railroad is magical so always towers $1$ and $3$ have $1$ visible adjacent railroads and they are always visible and the code is always $3$ (both railways are visible). By considering that the tour should contain the only architecture from both scenes from tower $1$ and $3$, and also the fact that we should return to the same tower, its best to go from $1$ to $3$ and return back to $1$ again. ## Sample input 2 ``` 4 6 0 1 2 0 2 3 0 3 4 0 4 1 1 1 3 1 2 4 ``` ## Sample output 2 ``` 4 1 63 4 4 47 2 2 63 3 3 31 1 ``` ## Sample input 3 ``` 3 2 0 1 2 1 2 3 ``` ## Sample output 3 ``` 4 1 3 3 3 3 1 1 1 2 2 1 1 ```

حل سؤال در بانک سؤالات