You are given a simple bidirectional bipartite graph with nodes and edges where every node has degree . Larry and Theo are fighting again, and have decided to settle things by playing a game on this graph. They will take turns adding edges to this graph (such that the graph remains simple), starting with Larry. Whoever's edge addition results in the graph being no longer bipartite loses. Determine who wins the game, assuming Larry and Theo play optimally as they always do.
Note that a simple graph is a graph without self-loops (edges from a node to itself) and multiple edges between a pair of nodes.
Note that a bipartite graph is a graph where the nodes can be partitioned into two sets and such that there are no edges between the nodes of , and no edges between the nodes of (i.e. all edges are between a node in and a node in ).
Input Specification
The first line of input contains two integers , the number of nodes and the number of edges in the original graph.
The next lines contain two integers indicating an edge connecting and .
Output Specification
On one line you are to output Larry
if Larry wins, or Theo
otherwise.
Subtasks
Subtask 1 (10%)
The graph is guaranteed to be connected.
Subtask 2 (90%)
No further constraints.
Sample Input
4 2
1 2
3 4
Sample Output
Theo
Note that you do not need to pass the sample to pass subtask 1.
Comments