Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Суперпозиция

(Время: 3 сек. Память: 32 Мб Сложность: 77%)

Гиптопод Поликарп – существо, прибывшее то ли из будущего, то ли из другого измерения, предоставил человечеству какой-то аппарат, который является то ли квантовым компьютером, то ли вечным двигателем.

Точнее, пока лишь он предоставил схему этого аппарата. На схеме присутствуют N точек и M каналов. Каждый канал соединяет ровно две точки и имеет заряд: «+» или «-». На некоторых каналах заряд находится в суперпозиции «?», то есть пока неизвестен.

Гиптопод Поликарп очень любит циклы, поэтому загадал загадку: сколькими способами можно установить все неизвестные заряды, чтобы все простые циклы на схеме были отрицательными?

Простым циклом на схеме называется последовательность различных точек таких, что все соседние точки, а также первая и последняя, соединены существующим каналом, и каждый канал используется не более одного раза.

Простой цикл является отрицательным, если произведение зарядов каналов этого цикла даёт знак «-».

Поликарп понимает, что ответ может быть слишком большим, поэтому просит вывести его остаток от деления на число 111111111111111111 ((1018−1)/9).

Входные данные

Первая строка входного файла INPUT.TXT содержит два целых числа N и M – количество точек и каналов на схеме соответственно (1 ≤ N, M ≤ 2∙105).

Следующие M строк содержат описания каналов в виде пары целых чисел ai и bi (1 ≤ ai, bi ≤ N, ai≠bi), обозначающих номера точек, которые соединяет этот канал, а также символ, означающий заряд этого канала: «+», «-» или «?».

Выходные данные

В выходной файл OUTPUT.TXT выведите целое число – ответ на задачу.

Примеры

INPUT.TXTOUTPUT.TXT
13 3
1 2 ?
2 3 ?
3 1 ?
4
24 4
1 2 +
1 3 +
2 3 -
1 4 ?
2

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 ЕГЭ по информатике
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2021 / 2022
 2022 / 2023
 A. Ближайшее нечётное
 B. Бобры-Зомби
 C. CSV Reader
 D. Суперпозиция
 E. Системы счисления
 F. Раздел империи
 G. Крыша
 H. Хардкорный массив
 I. Виталя и Рома
 J. Квадратов много не бывает

Красноярский краевой Дворец пионеров, (c)2006 - 2025, ИНН 246305493507, E-mail: admin@acmp.ru



Картинки по запросу vaneda ботинки купить.