Optimizer
Contest: Educational Codeforces Round 64 (Rated for Div. 2)
Difficulty rating: 2700
Tags: graphs, greedy, hashing, implementation

Let's analyze a program written on some strange programming language. The variables in this language have names consisting of $$$1$$$ to $$$4$$$ characters, and each character is a lowercase or an uppercase Latin letter, or a digit. There is an extra constraint that the first character should not be a digit.

There are four types of operations in the program, each denoted by one of the characters: $, ^, # or &.

Each line of the program has one of the following formats:

- <lvalue>=<rvalue>, where <lvalue> and <rvalue> are valid variable names;
- <lvalue>=<arg1><op><arg2>, where <lvalue>, <arg1> and <arg2> are valid variable names, and <op> is an operation character.

The program is executed line-by-line, and the result of execution is stored in a variable having the name res. If res is never assigned in the program, then the result will be equal to the value of res before running the program.

Two programs are called equivalent if no matter which operations do characters $, ^, # and & denote (but, obviously, performing the same operation on the same arguments gives the same result) and which values do variables have before execution of program, the value of res after running the first program is equal to the value of res after running the second program (the programs are executed independently).

You are given a program consisting of $$$n$$$ lines. Your task is to write a program consisting of minimum possible number of lines that is equivalent to the program you are given.

Input format:
The first line contains one integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the number of lines in the program.

Then $$$n$$$ lines follow — the program itself. Each line corresponds to the format described in the statement and has no extra whitespaces.

Output format:
In the first line print $$$k$$$ — the minimum number of lines in the equivalent program.

Then print $$$k$$$ lines without any whitespaces — an equivalent program having exactly $$$k$$$ lines, in the same format it is described in the statement.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
4
c=aa#bb
d12=c
res=c^d12
tmp=aa$c

Example output:
2
aaaa=aa#bb
res=aaaa^aaaa

Example input:
2
max=aaaa$bbbb
min=bbbb^aaaa

Example output:
0

Editorial:
I could've explained the jury solution, however, after the contest I found a much easier and more understandable solution by one of the participants. I put one of jury's solutions under the spoiler along with a link to the solution I'm explaining.
Let's restate the problem in a more convinient way. Initially we are given some directed acyclic graph. Let there be nodes of two kinds:
1. For a direct set operation. These will have a single outgoing edge to another node.
2. For a binary operation. These will have two outgoing edges to other nodes. However, it's important which edge is the "left" one and which is the "right" one.
We also have to make dummy vertices for the variables which only appeared at the right side of some operation.
We are allowed to remove any direct set operations, we will simulate this by compressing the edges of the graph. Instead of doing ($$$b=a, c=b$$$), we'll do ($$$b=a, c=a$$$). Value-wise this is the same but variable $$$c$$$ don't rely on $$$b$$$ anymore, so $$$b$$$ might be deleted.
We'll build the entire graph line by line. Let's maintain array $$$var2node$$$ which will keep the current value of each variable. It will store the node itself. It's probably better to store both kinds of nodes in a separate array so that $$$var2node$$$ and the pointers to the ends of the edges could be integers.
If we encountered no "res" variable getting set, then the answer is 0.
Otherwise let's traverse from the node representing the current value of "res" to every reachable node. While building the graph we were compressing every unoptimal operation, thus all reachable nodes matter.
Finally, the last operation on "res" might have been just a direct set. That's unoptimal, so we'll handle that case separately.