using System; using System.Collections.Generic; using System.Collections; using System.Collections.Specialized; using System.Linq; using System.Text; using System.IO; using System.Reflection; using static System.Math; using System.Numerics; using System.Threading; using System.Runtime.CompilerServices; static class Program{ const int mod=(int)1e9+7; static void Main(){ Sc sc=new Sc(); try{ var s=sc.Ia; int n=s[0],m=s[1]; var li=new List>[n+1]; var a=new int[n+1][]; var g=new int[n+1][]; for(int i=1;i<=n;i++){ li[i]=new List>(); a[i]=new int[]{0,0,0}; g[i]=new int[]{0,0,0}; } var h=new int[26]; var ca=new char[m+1]; for(int i=0;i(); ca[i+1]=e3; li[e1].Add(ValueTuple.Create(e2,e3-'a',i+1)); li[e2].Add(ValueTuple.Create(e1,e3-'a',i+1)); h[e3-'a']++; } for(int i = 0;i>(); qu.Enqueue(ValueTuple.Create(1,0,0)); while(qu.Count>0){ var e=qu.Dequeue(); for(int j = 0;j(); while(f!=0){ lia.Add(a[z][f]); if(g[z][f]<0){ z=Abs(g[z][f]); f--; } else{z=Abs(g[z][f]);} } lia.Reverse(); var c=new int[lia.Count]; for(int i = 0;i>1&0x55555555); bits=(bits&0x33333333)+(bits>>2&0x33333333); bits=(bits&0x0f0f0f0f)+(bits>>4&0x0f0f0f0f); bits=(bits&0x00ff00ff)+(bits>>8&0x00ff00ff); return (int)((bits&0x0000ffff)+(bits>>16&0x0000ffff)); } } public class Sc{ public int I{get{return int.Parse(Console.ReadLine());}} public long L{get{return long.Parse(Console.ReadLine());}} public double D{get{return double.Parse(Console.ReadLine());}} public string S{get{return Console.ReadLine();}} public int[] Ia{get{return Array.ConvertAll(Console.ReadLine().Split(),int.Parse);}} public long[] La{get{return Array.ConvertAll(Console.ReadLine().Split(),long.Parse);}} public double[] Da{get{return Array.ConvertAll(Console.ReadLine().Split(),double.Parse);}} public string[] Sa{get{return Console.ReadLine().Split();}} public object[] Oa{get{return Console.ReadLine().Split();}} public int[] Ia2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),int.Parse);}} public int[] Ia3(string a,string b){return Array.ConvertAll((a+Console.ReadLine()+b).Split(),int.Parse);} public long[] La2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),long.Parse);}} public long[] La3(string a,string b){return Array.ConvertAll((a+Console.ReadLine()+b).Split(),long.Parse);} public double[] Da2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),double.Parse);}} public double[] Da3(string a,string b){return Array.ConvertAll((a+Console.ReadLine()+b).Split(),double.Parse);} public T[] Arr(int n,Func f){var a=new T[n];for(int i=0;i(int n,Func f){var a=new T[n];for(int i=0;i(int n,Func f){var a=new T[n];for(int i=0;i(int n,Func f){var a=new T[n];for(int i=0;i(){var s=Console.ReadLine().Split();return (Ct(s[0]),Ct(s[1]));} public (T1,T2) Tp2(){var s=Console.ReadLine().Split();return (Ct(s[0]),Ct(s[1]));} public (T,T,T) Tp3(){var s=Console.ReadLine().Split();return (Ct(s[0]),Ct(s[1]),Ct(s[2]));} public (T1,T1,T2) Tp3(){var s=Console.ReadLine().Split();return (Ct(s[0]),Ct(s[1]),Ct(s[2]));} private T Ct(string s){return (T)Convert.ChangeType(s,typeof(T));} }