One-Way Streets and the Postman

On a directed graph the parity rule becomes a balance rule. If all the edges lie in one piece when the directions are ignored, then:

• every node has in == out → "cycle";
• exactly one node has out - in == 1 and exactly one has in - out == 1, and all the others balance → "path", which runs from the first to the second;
• anything else → "none".

Write euler_kind_directed(n, edges), where each edge (u, v) runs from u to v. Nodes with no edges at all are ignored, and a graph with no edges counts as "cycle".

Examples

Input:  n = 3, edges = [(0, 1), (1, 2), (2, 0)]
Output: "cycle"

Input:  n = 3, edges = [(0, 1), (0, 2)]
Output: "none"
Explanation: node 0 sends out two more edges than it takes in.

Constraints

• 1 <= n <= 10**5, 0 <= len(edges) <= 2 * 10**5
• Edges may repeat.

Goals

• State the Eulerian conditions for a directed graph
• Compare in-degree with out-degree node by node
• Keep the connectivity test on the underlying undirected graph