special symbols. Instead, we use the generic symbol ‘$?$’ to mean the special symbols. The symbol ‘$?$’ is not a single symbol, but a general placeholder to mean a special symbol. We maintain a running list of special symbols (say $s_1, s_2, \ldots$) and whenever a new row containing ‘$?$’ is added to the table, we actually get a new symbol from the list and replace ‘$?$’ by the new symbol. For instance, suppose $\langle ?, u, u\rangle$ and $\langle ?, v, ?\rangle$ are the first two rows added to the table. Then, the actual rows added are $\langle s_1, u, u\rangle$ and $\langle s_2, u, s_3\rangle$. With the above discussion in mind, notice that two different instances of ‘$?$’ do not match with each other.

The output table $T$ is constructed as follows.

1.  For each vertex $u\in V$, add the following 20 rows. These are said to be rows corresponding to $u$.

    1.  Add the following row six times: $\langle 0, u, u\rangle$. \[type:AAA\]

    2.  Add a row $\langle ?, u, u\rangle$. It is called the [*critical*]{} row of $u$ and it plays a vital role in the construction. \[type:BBB\]

    3.  Add seven rows: $\langle ?, u, ?\rangle$. 