Proving Propositions

Interview

Time limit2sMemory limit128 MB

Summary

Given directed edges between letters, compute the transitive closure and print all reachable pairs excluding self-loops, sorted by letter order.

Level: Medium4 of 10
Topics: Graph, DFS, Sorting
Solved: No attempts yet

Problem

In mathematics and logic, propositions of the form "if P, then Q" are common. Such a proposition is written as P => Q. Here, P is the antecedent and Q is the consequent.

If both propositions P => Q and Q => R are true, then by syllogism P => R is also true. In this problem, you must find the propositions that can be proved using only the given true propositions and this rule.

Each proposition given in the input is already true, so it is also considered provable. However, propositions whose antecedent and consequent are the same, such as P => P, are always true but must not be printed.

Given N true propositions, write a program that finds every proposition that can be proved.

Input

The first line contains an integer N (1 <= N <= 10,000). Each of the next N lines contains one true proposition.

Each proposition has the form P => Q, with one space before and after =>. P and Q are each one uppercase or lowercase English letter. The same proposition may appear more than once.

Output

Print the number X of propositions to output on the first line. On each of the next X lines, print one provable proposition.

Sort the propositions by antecedent, and when the antecedents are the same, by consequent. The letter order is A, B, ..., Z, a, b, ..., z. Do not print propositions whose antecedent and consequent are the same.

Examples1

Example 1
Input
```
2
A => b
b => C
```
Expected output
```
3
A => C
A => b
b => C
```