17643 번 : Amusement Park 
 17643 번 
 17643 번 - Amusement Park 
 3 초 512 MB 31 15 8 57 . 143 % 
 You have been hired to supervise the project of a new amusement park . The park will have a special gimmick : directed slides that can get customers from one attraction to another quickly and in an entertaining way . 
 The park owner has given you the current project : a list of planned attractions and a list of slides that should be built between them . However , him being a businessman , he casually envisioned the impossible : among other things , he projected a slide coming from the Haunted Castle to the Roller Coaster , another from the Roller Coaster to the Drop Tower , and a third from the Drop Tower to the Haunted Castle . As the slides can only go downhill , it is evident why this is a problem . You don ’ t have the luxury of ignoring the laws of physics when building the park , so you have to request changes in the project . Maybe he would accept reversing the slide between the Drop Tower and the Haunted Castle ? 
 The project is a list of attractions and a list of directed slides . Each slide starts at one attraction and ends at another attraction . 
 A proposal is obtained from the project by reversing the directions of some slides ( possibly none or all of them ) . 
 A proposal is legal if there is a way to assign an elevation to each attraction in such a way that every slide goes downhill . 
 The cost of a proposal is the number of slides whose directions were reversed . 
 For a given project , find and report the sum of costs all legal proposals . Since this number may be large , output it modulo 998 , 244 , 353 . 
 The first line contains two space - separated integers n , m ( 1 ≤ n ≤ 18 , 0 ≤ m ≤ n ( n − 1 ) / 2 ) – the number of attractions and the number of slides , respectively . The attractions are numbered 1 through n . 
 Then , m lines follow . The i - th of these lines contains two space - separated integers ai , bi ( 1 ≤ ai , bi ≤ n ) denoting a slide from ai to bi . You may assume that : 
 There are no self - loops . ( For each i : ai ≠ bi . ) 
 No slide appears twice . ( For all i ≠ j : ai ≠ aj or bi ≠ bj . ) 
 Output one line with a single integer , the sum of costs of all legal proposals modulo 998 , 244 , 353 . 
 In the first example , there are two proposals : 
 The slide direction is not flipped . This proposal has cost 0 . 
 The slide direction is flipped . This proposal has cost 1 . 
 In the second example , there are eight proposals with the slide directions as follows : 
 1 → 2 , 2 → 3 , 1 → 3 ( cost 0 ) 
 1 → 2 , 2 → 3 , 3 → 1 ( cost 1 ) 
 1 → 2 , 3 → 2 , 1 → 3 ( cost 1 ) 
 1 → 2 , 3 → 2 , 3 → 1 ( cost 2 ) 
 2 → 1 , 2 → 3 , 1 → 3 ( cost 1 ) 
 2 → 1 , 2 → 3 , 3 → 1 ( cost 2 ) 
 2 → 1 , 3 → 2 , 1 → 3 ( cost 2 ) 
 2 → 1 , 3 → 2 , 3 → 1 ( cost 3 ) 
 Olympiad > Central European Olympiad in Informatics > CEOI 2019 4 번