LCC/Moose '20 Contest 4 S5 - Larry vs. Theo

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem types

You are given a simple bidirectional bipartite graph with N nodes and M edges where every node has degree \geq 1. 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 A and B such that there are no edges between the nodes of A, and no edges between the nodes of B (i.e. all edges are between a node in A and a node in B).

Input Specification

The first line of input contains two integers N\ (3 \leq N \leq 2\cdot 10^5), M\ (0 \leq M \leq 4\cdot 10^5), the number of nodes and the number of edges in the original graph.

The next M lines contain two integers a,b\ (1 \leq a,b \leq N), a\neq b indicating an edge connecting a and b.

Output Specification

On one line you are to output Larry if Larry wins, or Theo otherwise.


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


Note that you do not need to pass the sample to pass subtask 1.


There are no comments at the moment.