F. Wizard's Tour

Codeforces

IDCF858F

Time2000ms

Memory256MB

Difficulty—

constructive algorithmsdfs and similargraphs

All Berland residents are waiting for an unprecedented tour of wizard in his Blue Helicopter over the cities of Berland! It is well-known that there are _n_ cities in Berland, some pairs of which are connected by bidirectional roads. Each pair of cities is connected by no more than one road. It is not guaranteed that the road network is _connected_, i.e. it is possible that you can't reach some city from some other. The tour will contain several episodes. In each of the episodes: * the wizard will disembark at some city _x_ from the Helicopter; * he will give a performance and show a movie for free at the city _x_; * he will drive to some neighboring city _y_ using a road; * he will give a performance and show a movie for free at the city _y_; * he will drive to some neighboring to _y_ city _z_; * he will give a performance and show a movie for free at the city _z_; * he will embark the Helicopter and fly away from the city _z_. It is known that the wizard doesn't like to use roads, so he agrees to use each road at most once (regardless of direction). In other words, for road between _a_ and _b_ he only can drive once from _a_ to _b_, or drive once from _b_ to _a_, or do not use this road at all. The wizards wants to plan as many episodes as possible without violation the above rules. Help the wizard! Please note that the wizard can visit the same city multiple times, the restriction is on roads only. ## Input The first line contains two integers _n_, _m_ (1 ≤ _n_ ≤ 2·105, 0 ≤ _m_ ≤ 2·105) — the number of cities and the number of roads in Berland, respectively. The roads description follow, one in each line. Each description is a pair of two integers _a__i_, _b__i_ (1 ≤ _a__i_, _b__i_ ≤ _n_, _a__i_ ≠ _b__i_), where _a__i_ and _b__i_ are the ids of the cities connected by the _i_\-th road. It is guaranteed that there are no two roads connecting the same pair of cities. Every road is bidirectional. The cities are numbered from 1 to _n_. It is possible that the road network in Berland is not connected. ## Output In the first line print _w_ — the maximum possible number of episodes. The next _w_ lines should contain the episodes in format _x_, _y_, _z_ — the three integers denoting the ids of the cities in the order of the wizard's visits. [samples]

Samples

Input #1

Output #1

2
1 4 2
4 3 2

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "F. Wizard's Tour",
    "description": {
      "content": "All Berland residents are waiting for an unprecedented tour of wizard in his Blue Helicopter over the cities of Berland! It is well-known that there are _n_ cities in Berland, some pairs of which are",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF858F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "All Berland residents are waiting for an unprecedented tour of wizard in his Blue Helicopter over the cities of Berland!\n\nIt is well-known that there are _n_ cities in Berland, some pairs of which are...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments