#!/bin/local/ruby
# 予約語から最長のしりとりを作ろう！(2回目)
# 言語    ：Ruby 1.9.3 or later
# OS      ：Windows Vista (ideone.comで動作確認済み time:1.8s)
# コメント：1回目の回答では、組み合わせ探索に膨大な時間がかかるため、省力化に乱択を使っていましたが、
#           今回は、しりとりを有向グラフおよびネットワークと見なし、線形計画法(シンプレックス法)を使って最適解を
#           求めました。最適解から使用する単語と始点を求め、使用する単語から閉路を抽出。残った単語で経路を作り、
#           最後に閉路を組み込むことで、最長となるしりとりを作りました。
#
# 参考文献：Vol.46 No.SIG 2(TOM 11) 情報処理学会論文誌：数理モデル化と応用「最長しりとり問題の解法」Jan.2005
#
# 回答：(35個)
#       alignas
#       signed
#       dynamic_cast
#       throw
#       while
#       extern
#       new
#       wchar_t
#       this
#       static
#       class
#       sizeof
#       friend
#       do
#       operator
#       reinterpret_cast
#       thread_local
#       long
#       goto
#       or
#       register
#       return
#       noexcept
#       typeid
#       default
#       true
#       export
#       template
#       explicit
#       typedef
#       float
#       typename
#       enum
#       mutable
#       else

# 単語定義
Word = [
"and",
"alignof",
"asm",
"auto",
"and_eq",
"alignas",
"bitand",
"break",
"bool",
"bitor",
"case","continue",
"catch",
"compl",
"char","constexpr",
"class",
"char16_t","char32_t","const","const_cast",
"decltype","delete","double",
"do",
"default","dynamic_cast",
"else",
"enum",
"extern",
"explicit","export",
"friend",
"false",
"for",
"float",
"goto",
"inline",
"if",
"int",
"long",
"mutable",
"namespace",
"not_eq",
"nullptr",
"noexcept","not",
"new",
"or_eq",
"operator","or",
"public",
"protected",
"private",
"return",
"register",
"reinterpret_cast",
"static",
"signed",
"sizeof",
"switch",
"short","static_assert","static_cast","struct",
"typeid",
"template","true","typename",
"typedef",
"thread_local",
"this",
"throw",
"try",
"unsigned",
"using",
"union",
"void",
"volatile",
"virtual",
"while",
"wchar_t",
"xor_eq",
"xor",
]

# シンプレックス法パラメータ
$MAX_LOOP = 100 # 最大反復回数

# シンプレックス法
def simplex_method(st)
    max_row    = st.size-1
    max_column = st[0].size-1
    work       = nil
    new_st     = Marshal.load(Marshal.dump(st))
    for count in 1..$MAX_LOOP
        # Step1:ピボット列を求める。
        pivot_column = st[1].index(st[1][1..-2].min)
        if st[1][pivot_column] == 0 then # 解あり
            return st,0
        end

        # Step2:ピボット行を求める。
        min_constant = nil
        pivot_row    = nil
        max_row.times{|r|
            if st[r+1][pivot_column] > 0 then
                work = st[r+1][-1]/(st[r+1][pivot_column].to_f)
                if min_constant == nil or min_constant >= work then
                    min_constant = work
                    pivot_row    = r+1
                end
            end
        }
        if pivot_row == nil then # 解なし
            return st,-1
        end

        # Step3:ピボット行以外の全要素について、st[r][c] = st[r][c]-st[ピボット行][c]×st[r][ピボット列]/st[ピボット行][ピボット列]
        #       ピボット行の全要素について、st[ピボット行][c] = st[ピボット行][c]/st[ピボット行][ピボット列]
        pivot  = st[pivot_row][pivot_column].to_f
        max_row.times{|r|
            if r+1 != pivot_row then
                work = st[r+1][pivot_column]/pivot
                max_column.times{|c|new_st[r+1][c+1] -= st[pivot_row][c+1]*work}
            else
                max_column.times{|c|new_st[r+1][c+1] /= pivot}
            end
        }
        new_st[pivot_row][0],new_st[0][pivot_column] = new_st[0][pivot_column],new_st[pivot_row][0]
        st = new_st
    end

    if st[1][pivot_column] == 0 then # 解あり
        return st,0
    else                             # 反復回数オーバー
        return st,-2
    end

end

# シンプレックス表作成
def create_simplex_tableau(v_list,az_list)
    st = []
    az_keys = az_list.keys.sort

    # 0行目
    st1 = ["_Basis"]   # 基底
    az_keys.each{|az|st1 << "x" +az   } # xij:変数
    v_list.each {|v |st1 << "xS"+v    }
    v_list.each {|v |st1 << "x" +v+"T"}
    az_keys.each{|az|st1 << "S" +az   } # Sij:スラック変数
    v_list.each {|v |st1 << "SS"+v    }
    v_list.each {|v |st1 << "S" +v+"T"}
    st1 << "_Constant" # 定数項
    st << st1

    # 1行目(目的関数): 最大化 Σxij
    st2 = ["_Object"]  # 目的関数
    st1.each{|s|st2 << (s[0] == "x" ? -1 : 0)}
    st << st2

    # 3行目以降(制約条件)
    # 制約条件1: xij ≦ 先頭文字がi,末尾文字がjのワード数
    st1[1..-2].each{|s1|
        if s1[0] == "S" then
            st3 = [s1]
            st1[1..-2].each{|s2|st3 << (s1[1..2] == s2[1..2] ? 1 : 0)}
            st3 << (az_list[s1[1..2]] == nil ? 1 : az_list[s1[1..2]]["WORD"].size) # 定数項
            st << st3
        end
    }
    # 制約条件2: 各頂点の入力量と出力量が同じ
    v_list.each{|v|
        st4 = [v]
        st1[1..-2].each{|s1|
            if s1[0] == "x" then
                if s1[1] == v then
                    st4 << (s1[2] == v ? 0 : -1)
                else
                    st4 << (s1[2] == v ? 1 : 0)
                end
            else
                st4 << 0
            end
        }
        st4 << 0 # 定数項
        st << st4
    }
    # 制約条件3: 始点(S)の出力量は1,終点(T)の入力量は1
    ["S","T"].each{|v|
        st5 = [v]
        st1[1..-2].each{|s1|st5 << ((s1[0] == "x" and (s1[1] == v or s1[2] == v)) ? 1 : 0)}
        st5 << 1 # 定数項
        st << st5
    }

    return st
end

# 「頂点リスト」と「ワードの先頭文字と末尾文字の集合」を作成する。
def create_v_az_list(word)
    v_list  = [] # 頂点リスト
    az_list = {} # ワードの先頭文字と末尾文字の集合
    word.each{|w|
        az = w[0]+w[-1]
        if az_list[az] == nil then
            az_list[az] = {"WORD"  => []}
        end
        az_list[az]["WORD"] << w
        v_list += [w[0],w[-1]]
    }
    v_list.uniq!
    v_list.sort!

    return v_list,az_list
end

# 最適解より、しりとりで使用する「ワードの先頭文字と末尾文字の部分集合」を作成する
def create_az_subset(ans)
    ans2 = []
    ans.each{|r|
        if r[0][0] == "x" and r[0].size == 3 and r[-1] > 0 then
            ans2 << [r[0][1..2],r[-1].to_i]
        end
    }

    return ans2
end

# 閉路の抽出
def detect_loop(ans2,az_list)
    loop_data = [] # 閉路データが格納される
    stock     = [] # 閉路に含まれなかった残ワードが格納される
    ans2.each{|a|
        if az_list[a[0]] != nil then
            stock += az_list[a[0]]["WORD"][0..a[1]-1]
        end
    }
    stock.each{|s|
        if s[0] == s[-1] then
            loop_data << s
        end
    }
    stock -= loop_data
    stock2 = stock
    while stock2.size > 0
        flag = true
        while flag
            flag = false
            stock3 = []
            stock2.each{|s1|
                stock.each{|s2|
                    if s1[-1] == s2[0] then
                        if s1[0] == s2[-1] then
                            loop_data << s1+","+s2
                            delete_list = []
                            stock2.each{|s4|
                                s1.split(",").each{|s3|
                                    if s4.split(",").index(s3) != nil then
                                        delete_list << s4
                                        break
                                    end
                                }
                                if s4.split(",").index(s2) != nil then
                                    delete_list << s4
                                end
                            }
                            stock2 -= delete_list
                            s1.split(",").each{|s3|stock.delete(s3)}
                            stock.delete(s2)
                            flag = true
                            break
                        else
                            stock3 << s1+","+s2
                        end
                    end
                }
                break if flag
            }
        end
        stock2 = stock3
    end

    return loop_data,stock
end

# 始点ワードの選択
def select_start_word(ans2,stock)
    start_word = nil
    ans2.each{|a|
        if a[0][0] == "S" then
            stock.each{|s|
                if s[0] == a[0][-1] then
                    start_word = s
                    stock.delete(s)
                    break
                end
            }
            break if start_word != nil
        end
    }

    return start_word,stock
end

# 残ワードを連結する
def join_stock_word(word_list,stock)
    while stock.size > 0
        stock.each{|s|
            if word_list[-1] == s[0] then
                word_list += ","+s
                stock.delete(s)
                break
            end
        }
    end

    return word_list,stock
end

# 残ワードに閉路を組み込む
def join_loop(word_list,loop_data)
    word_list = word_list.split(",")
    while loop_data.size > 0
        flag = false
        for j in 0..loop_data.size-1
            ld = loop_data[j]
            for i in 0..word_list.size-1
                if word_list[i][-1] == ld[0] then
                    word_list.insert(i+1,ld.split(","))
                    word_list.flatten!
                    loop_data.delete(ld)
                    flag = true
                    break
                end
            end
            break if flag
            loop_data[j] = ld.split(",").rotate.join(",")
        end
    end

    return word_list,loop_data
end

#-------------------------------------------------------------------------------------------
# メイン
#-------------------------------------------------------------------------------------------

# 「頂点リスト」と「ワードの先頭文字と末尾文字の集合」を作成する。
v_list,az_list = create_v_az_list(Word)

# 線形計画法により最適解を求める。
simplex_tableau = create_simplex_tableau(v_list,az_list) # シンプレックス表を作成する
ans,status = simplex_method(simplex_tableau)             # シンプレックス法で最適解を求める
                                                         #   ans = 解, status = エラー情報(本プログラムでは、エラー処理は省略)

# 最適解より、しりとりで使用する「ワードの先頭文字と末尾文字の部分集合」を作成する
ans2 = create_az_subset(ans)

# 閉路の抽出
loop_data,stock = detect_loop(ans2,az_list)

# 始点ワードの選択
start_word,stock = select_start_word(ans2,stock)

# 残ワードを連結する
word_list,stock = join_stock_word(start_word,stock)

# 残ワードに閉路を組み込む
result,loop_data = join_loop(word_list,loop_data)

# 解出力
print result.join("\n"),"\n"