using System;

using System.Collections.Generic;

​

public class Test

{

    public static string GetSExpression(string s){

        bool[,] graph = new bool [26,26];

        HashSet<char> nodes = new HashSet<char>();

        //construct graph and check error E2: duplicate edges

        bool E2 = false;

        for(int i=1;i<s.Length;i+=6){

            int x = s[i]-'A', y = s[i+2]-'A';

            if(graph[x,y]) //duplicate edge

                E2 = true;

            graph[x,y] = true;

            nodes.Add(s[i]);

            nodes.Add(s[i+2]);

        }

        //check error E1: more than 2 children

        bool E1 = false;

        for(int i=0;i<26;i++){

            int count = 0; //number of child

            for(int j=0;j<26;j++){

                if(graph[i,j])

                    count++;

            }

            if(count>2)

                return "E1";

        }

        if(E2) return "E2"; //return E2 after checking E1

        //check E3: cycle present and E4: multiple roots

        int numOfRoots = 0;

        char root =' ';

        foreach(char node in nodes){ //only check char that in the tree

            for(int i=0;i<26;i++){

                if(graph[i,node-'A'])

                    break;

                if(i==25){

                    numOfRoots++;

                    root = node;

                    bool[] visited = new bool[26];

                    if(IsCycle(node, graph, visited))

                        return "E3";

                }

            }

        }

        if(numOfRoots==0) return "E3"; //if no root, must be a cycle

        if(numOfRoots>1) return "E4"; //if more than one roots

        if(root==' ') return "E5"; //if no edge in input string, invalid input error

        return GetExpressionHelper(root, graph);

    }

    //true means there is a cycle, false means no cycle

    private static bool IsCycle(char node, bool[,] graph, bool[] visited){

        if(visited[node-'A']) //node has already been visited, must has a cycle

            return true;

        visited[node-'A'] = true;

        for(int i=0;i<26;i++){

            if(graph[node-'A',i]){

                if(IsCycle((char)(i+'A'), graph, visited))

                    return true;

            }

        }

        return false;

    }

    //Recursive DFS to get the expression/construct the tree

    private static string GetExpressionHelper(char root, bool[,] graph){

        string left = "", right = ""; //if no children, left and right should be empty

        for(int i=0;i<26;i++){

            if(graph[root-'A',i]){

                left = GetExpressionHelper((char)(i+'A'), graph);

                for(int j=i+1;j<26;j++){

                    if(graph[root-'A',j]){

                        right = GetExpressionHelper((char)(j+'A') ,graph);

                        break;

                    }

                }

                break;

            }

        }

        return "("+root+left+right+")";

    }

    public static void Main()

    {

        Console.WriteLine(GetSExpression("(A,B) (A,C) (B,G) (C,H) (E,F) (B,D) (C,E)"));

    }

}