#P18282. London Underground
London Underground
London Underground
给定伦敦地铁的一张无向图,其中有 426 个站点以及 505 条双向连接。还给定一个初始站点集合。
你需要计算有多少种方法向该集合中加入更多站点(可以一个也不加入),使最终集合中的任意两个站点之间都没有直接连接。
如果某个站点在一种方法的最终集合中、而不在另一种方法的最终集合中,则这两种方法不同。
答案可能很大,请输出对 取模后的结果。
输入格式
第一行包含一个整数 ,其中 。
接下来 行,每行包含两个站点的名称,表示它们之间有一条双向连接。站名是由英文字母、下划线或数字组成的字符串。
所有测试中的图都完全相同,恰有 426 个站点、505 条无向边,且没有自环或重边。边的排列顺序及同一条边两端的书写顺序不影响图。
接下来一行包含一个整数 ,满足 ,表示初始集合中的站点数。
接下来 行,每行包含一个站名,表示初始集合中的一个站点。它们均属于给定图且互不相同。
如果初始集合已经包含一条边的两个端点,则无法通过添加站点消除冲突,此时答案为 。
输出格式
输出一个整数,表示合法扩充方法数对 取模的结果。
完整样例
下面给出原样例的全部 505 条边,没有使用省略号。也可下载 完整样例输入附件。
505
Baker_Street Regents_Park
Charing_Cross Embankment
Edgware_Road__Bakerloo_ Marylebone
Embankment Waterloo
Harlesden Willesden_Junction
Harrow_and_Wealdstone Kenton
Kensal_Green Queens_Park
Kenton South_Kenton
Kilburn_Park Maida_Vale
Lambeth_North Elephant_and_Castle
Maida_Vale Warwick_Avenue
Marylebone Baker_Street
North_Wembley Wembley_Central
Oxford_Circus Piccadilly_Circus
Paddington Edgware_Road__Bakerloo_
Piccadilly_Circus Charing_Cross
Queens_Park Kilburn_Park
Regents_Park Oxford_Circus
South_Kenton North_Wembley
Stonebridge_Park Harlesden
Warwick_Avenue Paddington
Waterloo Lambeth_North
Wembley_Central Stonebridge_Park
Willesden_Junction Kensal_Green
Barking Dagenham_Dock
Barking Upminster
Dagenham_Dock Purfleet
Dagenham_Dock Rainham
Fenchurch_Street Limehouse
Fenchurch_Street Stratford
Limehouse West_Ham
Liverpool_Street Stratford
Ockendon Chafford_Hundred
Stratford Barking
Upminster Ockendon
West_Ham Barking
Bank St__Pauls
Barkingside Fairlop
Bethnal_Green Liverpool_Street
Bond_Street Marble_Arch
Buckhurst_Hill Woodford
Chancery_Lane Holborn
Chigwell Roding_Valley
Debden Loughton
East_Acton North_Acton
Epping Theydon_Bois
Fairlop Hainault
Gants_Hill Newbury_Park
Grange_Hill Chigwell
Greenford Northolt
Hainault Grange_Hill
Hanger_Lane Perivale
Holborn Tottenham_Court_Road
Holland_Park Shepherds_Bush
Lancaster_Gate Queensway
Leyton Stratford
Leytonstone Leyton
Leytonstone Wanstead
Liverpool_Street Bank
Loughton Buckhurst_Hill
Marble_Arch Lancaster_Gate
Mile_End Bethnal_Green
Newbury_Park Barkingside
North_Acton Hanger_Lane
North_Acton West_Acton
Northolt South_Ruislip
Notting_Hill_Gate Holland_Park
Oxford_Circus Bond_Street
Perivale Greenford
Queensway Notting_Hill_Gate
Redbridge Gants_Hill
Ruislip_Gardens West_Ruislip
Shepherds_Bush White_City
Snaresbrook Leytonstone
South_Ruislip Ruislip_Gardens
South_Woodford Snaresbrook
St__Pauls Chancery_Lane
Stratford Mile_End
Theydon_Bois Debden
Tottenham_Court_Road Oxford_Circus
Wanstead Redbridge
West_Acton Ealing_Broadway
White_City East_Acton
Woodford South_Woodford
Aldgate Tower_Hill
Baker_Street Great_Portland_Street
Barbican Moorgate
Bayswater Paddington
Blackfriars Temple
Cannon_Street Mansion_House
Edgware_Road__Circle_District_Hammersmith_and_City_ Baker_Street
Embankment Westminster
Euston_Square Kings_Cross_St__Pancras
Farringdon Barbican
Gloucester_Road High_Street_Kensington
Goldhawk_Road Shepherds_Bush_Market
Great_Portland_Street Euston_Square
Hammersmith__Met__ Goldhawk_Road
High_Street_Kensington Notting_Hill_Gate
Kings_Cross_St__Pancras Farringdon
Ladbroke_Grove Westbourne_Park
Latimer_Road Ladbroke_Grove
Liverpool_Street Aldgate
Mansion_House Blackfriars
Monument Cannon_Street
Moorgate Liverpool_Street
Notting_Hill_Gate Bayswater
Paddington Edgware_Road__Circle_District_Hammersmith_and_City_
Royal_Oak Paddington
Shepherds_Bush_Market Wood_Lane
Sloane_Square South_Kensington
South_Kensington Gloucester_Road
St__James_s_Park Victoria
Temple Embankment
Tower_Hill Monument
Victoria Sloane_Square
Westbourne_Park Royal_Oak
Westminster St__James_s_Park
Wood_Lane Latimer_Road
Acton_Town Ealing_Common
Aldgate_East Tower_Hill
Barking East_Ham
Barons_Court Hammersmith__District_
Becontree Upney
Bow_Church Stepney_Green
Bow_Road Bow_Church
Bromley_by_Bow Bow_Road
Chiswick_Park Acton_Town
Dagenham_East Dagenham_Heathway
Dagenham_Heathway Becontree
Ealing_Common Ealing_Broadway
Earls_Court High_Street_Kensington
Earls_Court Kensington__Olympia_
Earls_Court West_Brompton
Earls_Court West_Kensington
East_Ham Upton_Park
East_Putney Southfields
Elm_Park Dagenham_East
Fulham_Broadway Parsons_Green
Gloucester_Road Earls_Court
Gunnersbury Kew_Gardens
Hammersmith__District_ Ravenscourt_Park
Hornchurch Elm_Park
Kew_Gardens Richmond
Parsons_Green Putney_Bridge
Plaistow West_Ham
Putney_Bridge East_Putney
Ravenscourt_Park Stamford_Brook
Southfields Wimbledon_Park
Stamford_Brook Turnham_Green
Stepney_Green Whitechapel
Turnham_Green Chiswick_Park
Turnham_Green Gunnersbury
Upminster Upminster_Bridge
Upminster_Bridge Hornchurch
Upney Barking
Upton_Park Plaistow
West_Brompton Fulham_Broadway
West_Ham Bromley_by_Bow
West_Kensington Barons_Court
Whitechapel Aldgate_East
Wimbledon_Park Wimbledon
Abbey_Road West_Ham
All_Saints Poplar
Beckton_Park Cyprus
Blackwall East_India
Bow_Church Devons_Road
Canary_Wharf Heron_Quays
Canning_Town Royal_Victoria
Canning_Town West_Silvertown
Crossharbour_and_London_Arena Mudchute
Custom_House Prince_Regent
Cutty_Sark_for_Maritime_Greenwich Greenwich
Cyprus Gallions_Reach
Deptford_Bridge Elverson_Road
Devons_Road Langdon_Park
East_India Canning_Town
Elverson_Road Lewisham
Gallions_Reach Beckton
Greenwich Deptford_Bridge
Heron_Quays South_Quay
Island_Gardens Cutty_Sark_for_Maritime_Greenwich
King_George_V Woolwich_Arsenal
Langdon_Park All_Saints
Limehouse Shadwell
London_City_Airport King_George_V
Mudchute Island_Gardens
Pontoon_Dock London_City_Airport
Poplar Blackwall
Poplar West_India_Quay
Poplar Westferry
Prince_Regent Royal_Albert
Pudding_Mill_Lane Bow_Church
Royal_Albert Beckton_Park
Royal_Victoria Custom_House
Shadwell Bank
Shadwell Tower_Gateway
South_Quay Crossharbour_and_London_Arena
Star_Lane Canning_Town
Stratford Pudding_Mill_Lane
Stratford Stratford_High_Street
Stratford_High_Street Abbey_Road
Stratford_International Stratford
West_Ham Star_Lane
West_India_Quay Canary_Wharf
West_Silvertown Pontoon_Dock
Westferry Limehouse
Acton_Main_Line Ealing_Broadway
Bond_Street Paddington
Brentwood Harold_Wood
Burnham Taplow
Canary_Wharf Custom_House
Chadwell_Heath Goodmayes
Custom_House Woolwich
Ealing_Broadway West_Ealing
Farringdon Tottenham_Court_Road
Forest_Gate Maryland
Gidea_Park Romford
Goodmayes Seven_Kings
Hanwell Southall
Harold_Wood Gidea_Park
Hayes_and_Harlington Heathrow_Terminals_1_2_3
Hayes_and_Harlington West_Drayton
Heathrow_Terminals_1_2_3 Heathrow_Terminal_4
Heathrow_Terminals_1_2_3 Heathrow_Terminal_5
Ilford Manor_Park
Iver Langley
Langley Slough
Liverpool_Street Farringdon
Maidenhead Twyford
Manor_Park Forest_Gate
Maryland Stratford
Paddington Acton_Main_Line
Romford Chadwell_Heath
Seven_Kings Ilford
Shenfield Brentwood
Slough Burnham
Southall Hayes_and_Harlington
Stratford Whitechapel
Taplow Maidenhead
Tottenham_Court_Road Bond_Street
Twyford Reading
West_Drayton Iver
West_Ealing Hanwell
Whitechapel Canary_Wharf
Whitechapel Liverpool_Street
Woolwich Abbey_Wood
Liverpool_Street Aldgate_East
Mile_End Bow_Road
Stepney_Green Mile_End
Baker_Street Bond_Street
Bermondsey Canada_Water
Bond_Street Green_Park
Canada_Water Canary_Wharf
Canary_Wharf North_Greenwich
Canning_Town West_Ham
Canons_Park Queensbury
Dollis_Hill Willesden_Green
Finchley_Road Swiss_Cottage
Green_Park Westminster
Kilburn West_Hampstead
Kingsbury Wembley_Park
London_Bridge Bermondsey
Neasden Dollis_Hill
North_Greenwich Canning_Town
Queensbury Kingsbury
Southwark London_Bridge
St__Johns_Wood Baker_Street
Stanmore Canons_Park
Swiss_Cottage St__Johns_Wood
Waterloo Southwark
Wembley_Park Neasden
West_Ham Stratford
West_Hampstead Finchley_Road
Westminster Waterloo
Willesden_Green Kilburn
Baker_Street Finchley_Road
Chalfont_and_Latimer Amersham
Chalfont_and_Latimer Chesham
Chorleywood Chalfont_and_Latimer
Croxley Watford
Eastcote Ruislip_Manor
Finchley_Road Wembley_Park
Harrow_on_the_Hill North_Harrow
Harrow_on_the_Hill West_Harrow
Hillingdon Uxbridge
Ickenham Hillingdon
Moor_Park Croxley
Moor_Park Rickmansworth
North_Harrow Pinner
Northwick_Park Harrow_on_the_Hill
Northwood Moor_Park
Northwood_Hills Northwood
Pinner Northwood_Hills
Preston_Road Northwick_Park
Rickmansworth Chorleywood
Ruislip Ickenham
Ruislip_Manor Ruislip
Wembley_Park Preston_Road
West_Harrow Eastcote
Angel Kings_Cross_St__Pancras
Archway Highgate
Balham Clapham_South
Bank Moorgate
Belsize_Park Hampstead
Borough London_Bridge
Brent_Cross Hendon_Central
Burnt_Oak Edgware
Camden_Town Chalk_Farm
Camden_Town Kentish_Town
Chalk_Farm Belsize_Park
Charing_Cross Leicester_Square
Clapham_Common Clapham_North
Clapham_North Stockwell
Clapham_South Clapham_Common
Colindale Burnt_Oak
Colliers_Wood Tooting_Broadway
East_Finchley Finchley_Central
East_Finchley Mill_Hill_East
Elephant_and_Castle Borough
Euston Camden_Town
Euston Mornington_Crescent
Finchley_Central West_Finchley
Golders_Green Brent_Cross
Goodge_Street Warren_Street
Hampstead Golders_Green
Hendon_Central Colindale
Highgate East_Finchley
Kennington Elephant_and_Castle
Kennington Nine_Elms
Kennington Waterloo
Kentish_Town Tufnell_Park
Kings_Cross_St__Pancras Euston
Leicester_Square Tottenham_Court_Road
London_Bridge Bank
Moorgate Old_Street
Morden South_Wimbledon
Mornington_Crescent Camden_Town
Nine_Elms Battersea_Power_Station
Old_Street Angel
Oval Kennington
South_Wimbledon Colliers_Wood
Stockwell Oval
Tooting_Bec Balham
Tooting_Broadway Tooting_Bec
Tottenham_Court_Road Goodge_Street
Totteridge_and_Whetstone High_Barnet
Tufnell_Park Archway
Warren_Street Euston
West_Finchley Woodside_Park
Woodside_Park Totteridge_and_Whetstone
Acton_Central Willesden_Junction
Anerley Norwood_Junction
Barking Barking_Riverside
Bethnal_Green Cambridge_Heath
Blackhorse_Road Walthamstow_Queens_Road
Brockley Honor_Oak_Park
Brondesbury West_Hampstead
Brondesbury_Park Brondesbury
Bruce_Grove White_Hart_Lane
Bush_Hill_Park Enfield_Town
Bushey Carpenders_Park
Caledonian_Road_and_Barnsbury Highbury_and_Islington
Cambridge_Heath London_Fields
Camden_Road Caledonian_Road_and_Barnsbury
Canada_Water Surrey_Quays
Canonbury Dalston_Junction
Canonbury Dalston_Kingsland
Carpenders_Park Hatch_End
Clapham_High_Street Wandsworth_Road
Clapton St_James_Street
Crouch_Hill Harringay_Green_Lanes
Dalston_Junction Haggerston
Dalston_Kingsland Hackney_Central
Denmark_Hill Clapham_High_Street
Edmonton_Green Bush_Hill_Park
Edmonton_Green Southbury
Emerson_Park Upminster
Finchley_Road_and_Frognal Hampstead_Heath
Forest_Hill Sydenham
Gospel_Oak Kentish_Town_West
Gospel_Oak Upper_Holloway
Gunnersbury South_Acton
Hackney_Central Homerton
Hackney_Downs Clapton
Hackney_Downs Rectory_Road
Hackney_Wick Stratford
Haggerston Hoxton
Hampstead_Heath Gospel_Oak
Harringay_Green_Lanes South_Tottenham
Hatch_End Headstone_Lane
Headstone_Lane Harrow_and_Wealdstone
Highams_Park Chingford
Highbury_and_Islington Canonbury
Homerton Hackney_Wick
Honor_Oak_Park Forest_Hill
Hoxton Shoreditch_High_Street
Imperial_Wharf Clapham_Junction
Kensal_Rise Brondesbury_Park
Kensington__Olympia_ West_Brompton
Kentish_Town_West Camden_Road
Kilburn_High_Road South_Hampstead
Leyton_Midland_Road Leytonstone_High_Road
Leytonstone_High_Road Wanstead_Park
London_Fields Hackney_Downs
New_Cross_Gate Brockley
Norwood_Junction West_Croydon
Peckham_Rye Denmark_Hill
Penge_West Anerley
Queens_Park Kilburn_High_Road
Queens_Road_Peckham Peckham_Rye
Rectory_Road Stoke_Newington
Romford Emerson_Park
Rotherhithe Canada_Water
Seven_Sisters Bruce_Grove
Shadwell Wapping
Shepherds_Bush Kensington__Olympia_
Shoreditch_High_Street Whitechapel
Silver_Street Edmonton_Green
South_Acton Acton_Central
South_Hampstead Euston
South_Tottenham Blackhorse_Road
Southbury Turkey_Street
St_James_Street Walthamstow_Central
Stamford_Hill Seven_Sisters
Stoke_Newington Stamford_Hill
Surrey_Quays New_Cross
Surrey_Quays New_Cross_Gate
Surrey_Quays Queens_Road_Peckham
Sydenham Crystal_Palace
Sydenham Penge_West
Theobalds_Grove Cheshunt
Turkey_Street Theobalds_Grove
Upper_Holloway Crouch_Hill
Walthamstow_Central Wood_Street
Walthamstow_Queens_Road Leyton_Midland_Road
Wandsworth_Road Clapham_Junction
Wanstead_Park Woodgrange_Park
Wapping Rotherhithe
Watford_High_Street Bushey
Watford_Junction Watford_High_Street
West_Brompton Imperial_Wharf
West_Hampstead Finchley_Road_and_Frognal
White_Hart_Lane Silver_Street
Whitechapel Shadwell
Willesden_Junction Kensal_Rise
Willesden_Junction Shepherds_Bush
Wood_Street Highams_Park
Woodgrange_Park Barking
Acton_Town South_Ealing
Alperton Sudbury_Town
Arnos_Grove Bounds_Green
Arsenal Holloway_Road
Boston_Manor Osterley
Bounds_Green Wood_Green
Caledonian_Road Kings_Cross_St__Pancras
Cockfosters Oakwood
Covent_Garden Leicester_Square
Ealing_Common North_Ealing
Earls_Court Barons_Court
Finsbury_Park Arsenal
Green_Park Hyde_Park_Corner
Hammersmith__District_ Turnham_Green
Hatton_Cross Heathrow_Terminal_4
Hatton_Cross Heathrow_Terminals_1_2_3
Holborn Covent_Garden
Holloway_Road Caledonian_Road
Hounslow_Central Hounslow_West
Hounslow_East Hounslow_Central
Hounslow_West Hatton_Cross
Hyde_Park_Corner Knightsbridge
Kings_Cross_St__Pancras Russell_Square
Knightsbridge South_Kensington
Leicester_Square Piccadilly_Circus
Manor_House Finsbury_Park
North_Ealing Park_Royal
Northfields Boston_Manor
Oakwood Southgate
Osterley Hounslow_East
Park_Royal Alperton
Piccadilly_Circus Green_Park
Rayners_Lane Eastcote
Russell_Square Holborn
South_Ealing Northfields
South_Harrow Rayners_Lane
South_Harrow Sudbury_Hill
Southgate Arnos_Grove
Sudbury_Town Sudbury_Hill
Turnham_Green Acton_Town
Turnpike_Lane Manor_House
Wood_Green Turnpike_Lane
Blackhorse_Road Tottenham_Hale
Finsbury_Park Highbury_and_Islington
Green_Park Victoria
Highbury_and_Islington Kings_Cross_St__Pancras
Oxford_Circus Green_Park
Pimlico Vauxhall
Seven_Sisters Finsbury_Park
Stockwell Brixton
Tottenham_Hale Seven_Sisters
Vauxhall Stockwell
Victoria Pimlico
Walthamstow_Central Blackhorse_Road
Warren_Street Oxford_Circus
Waterloo Bank
2
Baker_Street
Liverpool_Street
159589981